package com.yuufa.test.ex;

public class Ex3 {

    static final char[] digits = {
        '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 
        'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j',
        'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't',
        'u', 'v', 'w', 'x', 'y', 'z'};
    
    public static void main(String[] args) {
        
    }
    
    public static void sort(int[] s, int left, int right, int n) {
        if(left<=right) {
            int k = partition(s, left, right, n);
            sort(s, left, k-1, n);
            sort(s, k+1, right, n);
        }
    }
    
    public static int partition(int[] s, int left, int right, int n) {
        
        int pivot = s[left];
        int i = left;
        int j = right + 1;
        
        while(i<j) {
            while(++i<=right && s[i]<pivot);
            while(--j>=left && s[j]>pivot);
            
            if(i<j) {
                int t = s[i]; s[i] = s[j]; s[j] = t;
            }
        }
        
        s[left] = s[j]; s[j] = pivot;
        
        return j;
    }
    
    public static void permutation(char[] s, int first, int last, int n) {
        if(first == last) {
            for(int i=0;i<n;i++) {
                System.out.printf("%1c", s[i]);
            }
            System.out.println();
        } else {
            for(int i=first;i<=last;i++) {
                char tmp = s[first]; s[first] = s[i]; s[i] = tmp;
                permutation(s, first+1, last, n);
                tmp = s[first]; s[first] = s[i]; s[i] = tmp;
            }
        }
    }
    
    public static void toString(int i) {
        
        if(i < 16) {
            System.out.print(digits[i]);
        } else {
            toString(i>>4);
            System.out.print(digits[i&15]);
        }
    }

    public static String toUnsignedString(int i, int shift) {
        
        char[] buf = new char[32];
        int pos = 32;
        int radix = 1 << shift;
        int mask = radix - 1;
        
        do {
            buf[--pos] = digits[i & mask];
            i = i >>> shift;
        } while (i != 0);
        
        return new String(buf, pos, (32-pos));
    }
}

class BinarySearch {
    
    // do sort before search
    public static int binarySearch(int[] s, int left, int right, int key) {
        
        if (left <= right) {
            int middle = (left + right) / 2;

            if (s[middle] == key) {
                return middle;
            } else if (s[middle] > key) {
                return binarySearch(s, left, middle - 1, key);
            } else if (s[middle] < key) {
                return binarySearch(s, middle + 1, right, key);
            }
        }

        return -1;
    }
    
    // do sort before search
    public static void search(int[] s, int left, int right, int value) {
        
        boolean finish = false;
        
        while(left <= right && !finish ) {
            int middle = (left + right) / 2;
            if( s[middle] == value ) {
                System.out.println("key's index = " + middle);
                finish = true;
            } else if ( s[middle] > value ) {
                right = middle - 1;
            } else if ( s[middle] < value ) {
                left = middle + 1;
            }
        }
        
        if(!finish) {
            System.out.println("not found");
        }
    }
}

// 特殊註標值
class Circular_2 {
    static int n = 5;
    static int[] s = new int[n];
    static int front = 0;
    static int rear = n;
    // (n+1)%n == (0+1)%n 
    
    public static boolean isEmpty() {
        return front == 0 && rear == n;
    }
    
    public static boolean isFull() {
        return front == rear;
    }
    
    public static void enqueue(int v) throws Exception {
        if(isFull()) {
            throw new Exception("is full");
        } else {
            s[++rear%n] = v;
        }
    }
    
    public static int dequeue() throws Exception {
        if(isEmpty()) {
            throw new Exception("is empty");
        } else {
            int value = s[++front%n];
            
            if(rear == front) {
                front = 0; rear = n;
            }
            
            return value;
        }
    }
}

// flag
class Circular_1 {
    static int n = 5;
    static int[] s = new int[n];
    static int front = n - 1; 
    static int rear = n - 1;
    static boolean flag = false;
        
    public static boolean isEmpty() {
        return !flag && front == rear;
    }
    
    public static boolean isFull() {
        return flag;
    }
    
    public static int dequeue() throws Exception {
        if(isEmpty()) {
            throw new Exception("is empty");
        } else {
            flag = false;
            return s[++front%n];
        }
    }
    
    public static void enqueue(int v) throws Exception {
        if(isFull()) {
            throw new Exception("is full");
        } else {
            s[++rear%n] = v;
            if(rear == front) {
                flag = true;
            }
        }
    }
}

// n-1
class CircularQueue {
    static int n = 5;
    static int[] s = new int[n];
    static int front = 0;
    static int rear = 0;
    
    public static boolean isEmpty() {
        return front == rear;
    }
    
    public static boolean isFull() {
        return front == (rear + 1) % n;
    }
    
    public static void enqueue(int v) throws Exception {
        if(isFull()) {
            throw new Exception("is full");
        } else {
            s[++rear%n] = v;
        }
    }
    
    public static int dequeue() throws Exception {
        if(isEmpty()) {
            throw new Exception("is empty");
        } else {
            return s[++front%n];
        }
    }
    
    public static int top() throws Exception {
        if(isEmpty()) {
            throw new Exception("is empty");
        } else {
            return s[(front+1)%n];
        }
    }
}

// 考慮元素移動
class LinearQueue {
    static int n = 5;
    static int[] s = new int[n];
    static int front = -1;
    static int rear = -1;
    
    public static boolean isEmpty() {
        return front == rear;
    }
    
    public static boolean isFull() {
        return front == -1 && rear == (n-1);
    }
    
    public static void move() {
        
        for (int i = front + 1; i <= rear; i++) {
            s[i-front-1] = s[i];
        }
        rear = rear - front - 1;
        front = -1;
    }
    
    public static void enqueue(int v) throws Exception {
        if(isFull()) {
            throw new Exception("is full");
        } else if (rear == (n-1) && front != -1) {
            move();
        }
        s[++rear] = v;
    }
    
    public static int dequeue() throws Exception {
        if(isEmpty()) {
            throw new Exception("is empty");
        } else {
            return s[++front];
        }
    }
    
    public static int top() throws Exception {
        if(isEmpty()) {
            throw new Exception("is empty");
        } else {
            return s[front + 1];
        }
    }
}

class Stack {
    
    static int n = 5;
    static int[] s = new int[n];
    static int sp = -1;
    
    public static boolean isEmpty() {
        return sp == -1;
    }
    
    public static boolean isFull() {
        return sp == (n - 1);
    }
    
    public static void push(int v) throws Exception {
        if(isFull()) {
            throw new Exception("is full");
        } else {
            s[++sp] = v;
        }
    }
    
    public static int pop() throws Exception {
        if(isEmpty()) {
            throw new Exception("is empty");
        } else {
            return s[sp--];
        }
    }
    
    public static int top() throws Exception {
        if(isEmpty()) {
            throw new Exception("is empty");
        } else {
            return s[sp];
        }
    }
}

class DisjointSet {

    public static int[] makeset(int n) {

        int[] data = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            data[i] = i;
        }

        return data;
    }

    public static int find(int node, int[] data) {

        int j = node;

        while (data[j] != j) {
            j = data[j];
        }

        return j;
    }

    public static void merge(int p, int q, int[] data) {
        if (p < q) {
            data[q] = p;
        } else {
            data[p] = q;
        }
    }
}